import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-05
 * Time: 22:08
 */
public class TopVotedCandidate {
    private int[] times;
    private int[] candidate;
    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        int len = times.length;
        this.candidate = new int[len];
        int max = 0; // 记录当前最多的票数
        int person = persons[0]; // 记录当前最多票数对应的人
        Map<Integer, Integer> map = new HashMap<>(); // 记录每个人对应的票数
        for (int i = 0; i < len; i++) {
            // 先把当前这一票加进去
            map.put(persons[i], map.getOrDefault(persons[i], 0) + 1);
            if (map.get(persons[i]) >= max) {
                // 更新票数最多的人以票数
                max = map.get(persons[i]);
                person = persons[i];
            }
            // 记录当前票数最多的人
            candidate[i] = person;
        }
    }

    public int q(int t) {
        // 使用二分查找, 找到当前时间对应的下标
        int len = times.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = ((right-left+1) >> 1) + left;
            if (times[mid] > t) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 根据下标找到对应的人
        return candidate[right];
    }
}
